home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / Winding.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  16.2 KB  |  797 lines
  1.  
  2.  
  3. #include "stdafx.h"
  4. #include <assert.h>
  5. #include "qe3.h"
  6. #include "winding.h"
  7.  
  8. #define    BOGUS_RANGE    18000
  9.  
  10. /*
  11. =============
  12. Plane_Equal
  13. =============
  14. */
  15. #define    NORMAL_EPSILON    0.0001
  16. #define    DIST_EPSILON    0.02
  17.  
  18. int Plane_Equal(plane_t *a, plane_t *b, int flip)
  19. {
  20.     vec3_t normal;
  21.     float dist;
  22.  
  23.     if (flip) {
  24.         normal[0] = - b->normal[0];
  25.         normal[1] = - b->normal[1];
  26.         normal[2] = - b->normal[2];
  27.         dist = - b->dist;
  28.     }
  29.     else {
  30.         normal[0] = b->normal[0];
  31.         normal[1] = b->normal[1];
  32.         normal[2] = b->normal[2];
  33.         dist = b->dist;
  34.     }
  35.     if (
  36.        fabs(a->normal[0] - normal[0]) < NORMAL_EPSILON
  37.     && fabs(a->normal[1] - normal[1]) < NORMAL_EPSILON
  38.     && fabs(a->normal[2] - normal[2]) < NORMAL_EPSILON
  39.     && fabs(a->dist - dist) < DIST_EPSILON )
  40.         return true;
  41.     return false;
  42. }
  43.  
  44. /*
  45. ============
  46. Plane_FromPoints
  47. ============
  48. */
  49. int Plane_FromPoints(vec3_t p1, vec3_t p2, vec3_t p3, plane_t *plane)
  50. {
  51.     vec3_t v1, v2;
  52.  
  53.     VectorSubtract(p2, p1, v1);
  54.     VectorSubtract(p3, p1, v2);
  55.     //CrossProduct(v2, v1, plane->normal);
  56.     CrossProduct(v1, v2, plane->normal);
  57.     if (VectorNormalize(plane->normal) < 0.1) return false;
  58.     plane->dist = DotProduct(p1, plane->normal);
  59.     return true;
  60. }
  61.  
  62. /*
  63. =================
  64. Point_Equal
  65. =================
  66. */
  67. int Point_Equal(vec3_t p1, vec3_t p2, float epsilon)
  68. {
  69.     int i;
  70.  
  71.     for (i = 0; i < 3; i++)
  72.     {
  73.         if (fabs(p1[i] - p2[i]) > epsilon) return false;
  74.     }
  75.     return true;
  76. }
  77.  
  78.  
  79. /*
  80. =================
  81. Winding_BaseForPlane
  82. =================
  83. */
  84. winding_t *Winding_BaseForPlane (plane_t *p)
  85. {
  86.     int        i, x;
  87.     vec_t    max, v;
  88.     vec3_t    org, vright, vup;
  89.     winding_t    *w;
  90.     
  91.     // find the major axis
  92.  
  93.     max = -BOGUS_RANGE;
  94.     x = -1;
  95.     for (i=0 ; i<3; i++)
  96.     {
  97.         v = fabs(p->normal[i]);
  98.         if (v > max)
  99.         {
  100.             x = i;
  101.             max = v;
  102.         }
  103.     }
  104.     if (x==-1)
  105.         Error ("Winding_BaseForPlane: no axis found");
  106.         
  107.     VectorCopy (vec3_origin, vup);    
  108.     switch (x)
  109.     {
  110.     case 0:
  111.     case 1:
  112.         vup[2] = 1;
  113.         break;        
  114.     case 2:
  115.         vup[0] = 1;
  116.         break;        
  117.     }
  118.  
  119.  
  120.     v = DotProduct (vup, p->normal);
  121.     VectorMA (vup, -v, p->normal, vup);
  122.     VectorNormalize (vup);
  123.         
  124.     VectorScale (p->normal, p->dist, org);
  125.     
  126.     CrossProduct (vup, p->normal, vright);
  127.     
  128.     VectorScale (vup, BOGUS_RANGE, vup);
  129.     VectorScale (vright, BOGUS_RANGE, vright);
  130.  
  131.     // project a really big    axis aligned box onto the plane
  132.     w = Winding_Alloc (4);
  133.     
  134.     VectorSubtract (org, vright, w->points[0]);
  135.     VectorAdd (w->points[0], vup, w->points[0]);
  136.     
  137.     VectorAdd (org, vright, w->points[1]);
  138.     VectorAdd (w->points[1], vup, w->points[1]);
  139.     
  140.     VectorAdd (org, vright, w->points[2]);
  141.     VectorSubtract (w->points[2], vup, w->points[2]);
  142.     
  143.     VectorSubtract (org, vright, w->points[3]);
  144.     VectorSubtract (w->points[3], vup, w->points[3]);
  145.     
  146.     w->numpoints = 4;
  147.     
  148.     return w;    
  149. }
  150.  
  151. /*
  152. ==================
  153. Winding_Alloc
  154. ==================
  155. */
  156. winding_t *Winding_Alloc (int points)
  157. {
  158.     winding_t    *w;
  159.     int            size;
  160.     
  161.     if (points > MAX_POINTS_ON_WINDING)
  162.         Error ("Winding_Alloc: %i points", points);
  163.     
  164.     size = (int)((winding_t *)0)->points[points];
  165.     w = (winding_t*) malloc (size);
  166.     memset (w, 0, size);
  167.     w->maxpoints = points;
  168.     
  169.     return w;
  170. }
  171.  
  172.  
  173. void Winding_Free (winding_t *w)
  174. {
  175.     free(w);
  176. }
  177.  
  178.  
  179. /*
  180. ==================
  181. Winding_Clone
  182. ==================
  183. */
  184. winding_t *Winding_Clone(winding_t *w)
  185. {
  186.     int            size;
  187.     winding_t    *c;
  188.     
  189.     size = (int)((winding_t *)0)->points[w->numpoints];
  190.     c = (winding_t*)qmalloc (size);
  191.     memcpy (c, w, size);
  192.     return c;
  193. }
  194.  
  195. /*
  196. ==================
  197. ReverseWinding
  198. ==================
  199. */
  200. winding_t *Winding_Reverse(winding_t *w)
  201. {
  202.     int            i;
  203.     winding_t    *c;
  204.  
  205.     c = Winding_Alloc(w->numpoints);
  206.     for (i = 0; i < w->numpoints; i++)
  207.     {
  208.         VectorCopy (w->points[w->numpoints-1-i], c->points[i]);
  209.     }
  210.     c->numpoints = w->numpoints;
  211.     return c;
  212. }
  213.  
  214.  
  215. /*
  216. ==============
  217. Winding_RemovePoint
  218. ==============
  219. */
  220. void Winding_RemovePoint(winding_t *w, int point)
  221. {
  222.     if (point < 0 || point >= w->numpoints)
  223.         Error("Winding_RemovePoint: point out of range");
  224.  
  225.     if (point < w->numpoints-1)
  226.     {
  227.         memmove(&w->points[point], &w->points[point+1], (int)((winding_t *)0)->points[w->numpoints - point - 1]);
  228.     }
  229.     w->numpoints--;
  230. }
  231.  
  232. /*
  233. =============
  234. Winding_InsertPoint
  235. =============
  236. */
  237. winding_t *Winding_InsertPoint(winding_t *w, vec3_t point, int spot)
  238. {
  239.     int i, j;
  240.     winding_t *neww;
  241.  
  242.     if (spot > w->numpoints)
  243.     {
  244.         Error("Winding_InsertPoint: spot > w->numpoints");
  245.     } //end if
  246.     if (spot < 0)
  247.     {
  248.         Error("Winding_InsertPoint: spot < 0");
  249.     } //end if
  250.     neww = Winding_Alloc(w->numpoints + 1);
  251.     neww->numpoints = w->numpoints + 1;
  252.     for (i = 0, j = 0; i < neww->numpoints; i++)
  253.     {
  254.         if (i == spot)
  255.         {
  256.             VectorCopy(point, neww->points[i]);
  257.         }
  258.         else
  259.         {
  260.             VectorCopy(w->points[j], neww->points[i]);
  261.             j++;
  262.         }
  263.     }
  264.     return neww;
  265. }
  266.  
  267. /*
  268. ==============
  269. Winding_IsTiny
  270. ==============
  271. */
  272. #define    EDGE_LENGTH    0.2
  273.  
  274. int Winding_IsTiny (winding_t *w)
  275. {
  276.     int        i, j;
  277.     vec_t    len;
  278.     vec3_t    delta;
  279.     int        edges;
  280.  
  281.     edges = 0;
  282.     for (i=0 ; i<w->numpoints ; i++)
  283.     {
  284.         j = i == w->numpoints - 1 ? 0 : i+1;
  285.         VectorSubtract (w->points[j], w->points[i], delta);
  286.         len = VectorLength (delta);
  287.         if (len > EDGE_LENGTH)
  288.         {
  289.             if (++edges == 3)
  290.                 return false;
  291.         }
  292.     }
  293.     return true;
  294. }
  295.  
  296. /*
  297. ==============
  298. Winding_IsHuge
  299. ==============
  300. */
  301. int Winding_IsHuge(winding_t *w)
  302. {
  303.     int        i, j;
  304.  
  305.     for (i=0 ; i<w->numpoints ; i++)
  306.     {
  307.         for (j=0 ; j<3 ; j++)
  308.             if (w->points[i][j] < -BOGUS_RANGE+1 || w->points[i][j] > BOGUS_RANGE-1)
  309.                 return true;
  310.     }
  311.     return false;
  312. }
  313.  
  314. /*
  315. =============
  316. Winding_PlanesConcave
  317. =============
  318. */
  319. #define WCONVEX_EPSILON        0.2
  320.  
  321. int Winding_PlanesConcave(winding_t *w1, winding_t *w2,
  322.                              vec3_t normal1, vec3_t normal2,
  323.                              float dist1, float dist2)
  324. {
  325.     int i;
  326.  
  327.     if (!w1 || !w2) return false;
  328.  
  329.     // check if one of the points of winding 1 is at the back of the plane of winding 2
  330.     for (i = 0; i < w1->numpoints; i++)
  331.     {
  332.         if (DotProduct(normal2, w1->points[i]) - dist2 > WCONVEX_EPSILON) return true;
  333.     }
  334.     // check if one of the points of winding 2 is at the back of the plane of winding 1
  335.     for (i = 0; i < w2->numpoints; i++)
  336.     {
  337.         if (DotProduct(normal1, w2->points[i]) - dist1 > WCONVEX_EPSILON) return true;
  338.     }
  339.  
  340.     return false;
  341. }
  342.  
  343. /*
  344. ==================
  345. Winding_Clip
  346.  
  347. Clips the winding to the plane, returning the new winding on the positive side
  348. Frees the input winding.
  349. If keepon is true, an exactly on-plane winding will be saved, otherwise
  350. it will be clipped away.
  351. ==================
  352. */
  353. winding_t *Winding_Clip (winding_t *in, plane_t *split, qboolean keepon)
  354. {
  355.     vec_t    dists[MAX_POINTS_ON_WINDING];
  356.     int        sides[MAX_POINTS_ON_WINDING];
  357.     int        counts[3];
  358.     vec_t    dot;
  359.     int        i, j;
  360.     vec_t    *p1, *p2;
  361.     vec3_t    mid;
  362.     winding_t    *neww;
  363.     int        maxpts;
  364.     
  365.     counts[0] = counts[1] = counts[2] = 0;
  366.  
  367.     // determine sides for each point
  368.     for (i=0 ; i<in->numpoints ; i++)
  369.     {
  370.         dot = DotProduct (in->points[i], split->normal);
  371.         dot -= split->dist;
  372.         dists[i] = dot;
  373.         if (dot > ON_EPSILON)
  374.             sides[i] = SIDE_FRONT;
  375.         else if (dot < -ON_EPSILON)
  376.             sides[i] = SIDE_BACK;
  377.         else
  378.         {
  379.             sides[i] = SIDE_ON;
  380.         }
  381.         counts[sides[i]]++;
  382.     }
  383.     sides[i] = sides[0];
  384.     dists[i] = dists[0];
  385.     
  386.     if (keepon && !counts[0] && !counts[1])
  387.         return in;
  388.         
  389.     if (!counts[0])
  390.     {
  391.         Winding_Free (in);
  392.         return NULL;
  393.     }
  394.     if (!counts[1])
  395.         return in;
  396.     
  397.     maxpts = in->numpoints+4;    // can't use counts[0]+2 because
  398.                                 // of fp grouping errors
  399.     neww = Winding_Alloc (maxpts);
  400.         
  401.     for (i=0 ; i<in->numpoints ; i++)
  402.     {
  403.         p1 = in->points[i];
  404.         
  405.         if (sides[i] == SIDE_ON)
  406.         {
  407.             VectorCopy (p1, neww->points[neww->numpoints]);
  408.             neww->numpoints++;
  409.             continue;
  410.         }
  411.     
  412.         if (sides[i] == SIDE_FRONT)
  413.         {
  414.             VectorCopy (p1, neww->points[neww->numpoints]);
  415.             neww->numpoints++;
  416.         }
  417.         
  418.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  419.             continue;
  420.             
  421.         // generate a split point
  422.         p2 = in->points[(i+1)%in->numpoints];
  423.         
  424.         dot = dists[i] / (dists[i]-dists[i+1]);
  425.         for (j=0 ; j<3 ; j++)
  426.         {    // avoid round off error when possible
  427.             if (split->normal[j] == 1)
  428.                 mid[j] = split->dist;
  429.             else if (split->normal[j] == -1)
  430.                 mid[j] = -split->dist;
  431.             else
  432.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  433.         }
  434.             
  435.         VectorCopy (mid, neww->points[neww->numpoints]);
  436.         neww->numpoints++;
  437.     }
  438.     
  439.     if (neww->numpoints > maxpts)
  440.         Error ("Winding_Clip: points exceeded estimate");
  441.         
  442.     // free the original winding
  443.     Winding_Free (in);
  444.     
  445.     return neww;
  446. }
  447.  
  448. /*
  449. =============
  450. Winding_SplitEpsilon
  451.  
  452.   split the input winding with the plane
  453.   the input winding stays untouched
  454. =============
  455. */
  456. void Winding_SplitEpsilon (winding_t *in, vec3_t normal, double dist, 
  457.                 vec_t epsilon, winding_t **front, winding_t **back)
  458. {
  459.     vec_t    dists[MAX_POINTS_ON_WINDING+4];
  460.     int        sides[MAX_POINTS_ON_WINDING+4];
  461.     int        counts[3];
  462.     vec_t    dot;
  463.     int        i, j;
  464.     vec_t    *p1, *p2;
  465.     vec3_t    mid;
  466.     winding_t    *f, *b;
  467.     int        maxpts;
  468.     
  469.     counts[0] = counts[1] = counts[2] = 0;
  470.  
  471.     // determine sides for each point
  472.     for (i = 0; i < in->numpoints; i++)
  473.     {
  474.         dot = DotProduct (in->points[i], normal);
  475.         dot -= dist;
  476.         dists[i] = dot;
  477.         if (dot > epsilon)
  478.             sides[i] = SIDE_FRONT;
  479.         else if (dot < -epsilon)
  480.             sides[i] = SIDE_BACK;
  481.         else
  482.         {
  483.             sides[i] = SIDE_ON;
  484.         }
  485.         counts[sides[i]]++;
  486.     }
  487.     sides[i] = sides[0];
  488.     dists[i] = dists[0];
  489.     
  490.     *front = *back = NULL;
  491.  
  492.     if (!counts[0])
  493.     {
  494.         *back = Winding_Clone(in);
  495.         return;
  496.     }
  497.     if (!counts[1])
  498.     {
  499.         *front = Winding_Clone(in);
  500.         return;
  501.     }
  502.  
  503.     maxpts = in->numpoints+4;    // cant use counts[0]+2 because
  504.                                 // of fp grouping errors
  505.  
  506.     *front = f = Winding_Alloc (maxpts);
  507.     *back = b = Winding_Alloc (maxpts);
  508.         
  509.     for (i = 0; i < in->numpoints; i++)
  510.     {
  511.         p1 = in->points[i];
  512.         
  513.         if (sides[i] == SIDE_ON)
  514.         {
  515.             VectorCopy (p1, f->points[f->numpoints]);
  516.             f->numpoints++;
  517.             VectorCopy (p1, b->points[b->numpoints]);
  518.             b->numpoints++;
  519.             continue;
  520.         }
  521.     
  522.         if (sides[i] == SIDE_FRONT)
  523.         {
  524.             VectorCopy (p1, f->points[f->numpoints]);
  525.             f->numpoints++;
  526.         }
  527.         if (sides[i] == SIDE_BACK)
  528.         {
  529.             VectorCopy (p1, b->points[b->numpoints]);
  530.             b->numpoints++;
  531.         }
  532.  
  533.         if (sides[i+1] == SIDE_ON || sides[i+1] == sides[i])
  534.             continue;
  535.             
  536.         // generate a split point
  537.         p2 = in->points[(i+1)%in->numpoints];
  538.         
  539.         dot = dists[i] / (dists[i]-dists[i+1]);
  540.         for (j = 0; j < 3; j++)
  541.         {
  542.             // avoid round off error when possible
  543.             if (normal[j] == 1)
  544.                 mid[j] = dist;
  545.             else if (normal[j] == -1)
  546.                 mid[j] = -dist;
  547.             else
  548.                 mid[j] = p1[j] + dot*(p2[j]-p1[j]);
  549.         }
  550.             
  551.         VectorCopy (mid, f->points[f->numpoints]);
  552.         f->numpoints++;
  553.         VectorCopy (mid, b->points[b->numpoints]);
  554.         b->numpoints++;
  555.     }
  556.     
  557.     if (f->numpoints > maxpts || b->numpoints > maxpts)
  558.         Error ("Winding_Clip: points exceeded estimate");
  559.     if (f->numpoints > MAX_POINTS_ON_WINDING || b->numpoints > MAX_POINTS_ON_WINDING)
  560.         Error ("Winding_Clip: MAX_POINTS_ON_WINDING");
  561. }
  562.  
  563. /*
  564. =============
  565. Winding_TryMerge
  566.  
  567. If two windings share a common edge and the edges that meet at the
  568. common points are both inside the other polygons, merge them
  569.  
  570. Returns NULL if the windings couldn't be merged, or the new winding.
  571. The originals will NOT be freed.
  572.  
  573. if keep is true no points are ever removed
  574. =============
  575. */
  576. #define    CONTINUOUS_EPSILON    0.005
  577.  
  578. winding_t *Winding_TryMerge(winding_t *f1, winding_t *f2, vec3_t planenormal, int keep)
  579. {
  580.     vec_t        *p1, *p2, *p3, *p4, *back;
  581.     winding_t    *newf;
  582.     int            i, j, k, l;
  583.     vec3_t        normal, delta;
  584.     vec_t        dot;
  585.     qboolean    keep1, keep2;
  586.     
  587.  
  588.     //
  589.     // find a common edge
  590.     //    
  591.     p1 = p2 = NULL;    // stop compiler warning
  592.     j = 0;            // 
  593.     
  594.     for (i = 0; i < f1->numpoints; i++)
  595.     {
  596.         p1 = f1->points[i];
  597.         p2 = f1->points[(i+1) % f1->numpoints];
  598.         for (j = 0; j < f2->numpoints; j++)
  599.         {
  600.             p3 = f2->points[j];
  601.             p4 = f2->points[(j+1) % f2->numpoints];
  602.             for (k = 0; k < 3; k++)
  603.             {
  604.                 if (fabs(p1[k] - p4[k]) > 0.1)//EQUAL_EPSILON) //ME
  605.                     break;
  606.                 if (fabs(p2[k] - p3[k]) > 0.1)//EQUAL_EPSILON) //ME
  607.                     break;
  608.             } //end for
  609.             if (k==3)
  610.                 break;
  611.         } //end for
  612.         if (j < f2->numpoints)
  613.             break;
  614.     } //end for
  615.     
  616.     if (i == f1->numpoints)
  617.         return NULL;            // no matching edges
  618.  
  619.     //
  620.     // check slope of connected lines
  621.     // if the slopes are colinear, the point can be removed
  622.     //
  623.     back = f1->points[(i+f1->numpoints-1)%f1->numpoints];
  624.     VectorSubtract (p1, back, delta);
  625.     CrossProduct (planenormal, delta, normal);
  626.     VectorNormalize (normal);
  627.     
  628.     back = f2->points[(j+2)%f2->numpoints];
  629.     VectorSubtract (back, p1, delta);
  630.     dot = DotProduct (delta, normal);
  631.     if (dot > CONTINUOUS_EPSILON)
  632.         return NULL;            // not a convex polygon
  633.     keep1 = (qboolean)(dot < -CONTINUOUS_EPSILON);
  634.     
  635.     back = f1->points[(i+2)%f1->numpoints];
  636.     VectorSubtract (back, p2, delta);
  637.     CrossProduct (planenormal, delta, normal);
  638.     VectorNormalize (normal);
  639.  
  640.     back = f2->points[(j+f2->numpoints-1)%f2->numpoints];
  641.     VectorSubtract (back, p2, delta);
  642.     dot = DotProduct (delta, normal);
  643.     if (dot > CONTINUOUS_EPSILON)
  644.         return NULL;            // not a convex polygon
  645.     keep2 = (qboolean)(dot < -CONTINUOUS_EPSILON);
  646.  
  647.     //
  648.     // build the new polygon
  649.     //
  650.     newf = Winding_Alloc (f1->numpoints + f2->numpoints);
  651.     
  652.     // copy first polygon
  653.     for (k=(i+1)%f1->numpoints ; k != i ; k=(k+1)%f1->numpoints)
  654.     {
  655.         if (!keep && k==(i+1)%f1->numpoints && !keep2)
  656.             continue;
  657.         
  658.         VectorCopy (f1->points[k], newf->points[newf->numpoints]);
  659.         newf->numpoints++;
  660.     }
  661.     
  662.     // copy second polygon
  663.     for (l= (j+1)%f2->numpoints ; l != j ; l=(l+1)%f2->numpoints)
  664.     {
  665.         if (!keep && l==(j+1)%f2->numpoints && !keep1)
  666.             continue;
  667.         VectorCopy (f2->points[l], newf->points[newf->numpoints]);
  668.         newf->numpoints++;
  669.     }
  670.  
  671.     return newf;
  672. }
  673.  
  674. /*
  675. ============
  676. Winding_Plane
  677. ============
  678. */
  679. void Winding_Plane (winding_t *w, vec3_t normal, double *dist)
  680. {
  681.     vec3_t v1, v2;
  682.     int i;
  683.  
  684.     //find two vectors each longer than 0.5 units
  685.     for (i = 0; i < w->numpoints; i++)
  686.     {
  687.         VectorSubtract(w->points[(i+1) % w->numpoints], w->points[i], v1);
  688.         VectorSubtract(w->points[(i+2) % w->numpoints], w->points[i], v2);
  689.         if (VectorLength(v1) > 0.5 && VectorLength(v2) > 0.5) break;
  690.     }
  691.     CrossProduct(v2, v1, normal);
  692.     VectorNormalize(normal);
  693.     *dist = DotProduct(w->points[0], normal);
  694. }
  695.  
  696. /*
  697. =============
  698. Winding_Area
  699. =============
  700. */
  701. float Winding_Area (winding_t *w)
  702. {
  703.     int        i;
  704.     vec3_t    d1, d2, cross;
  705.     float    total;
  706.  
  707.     total = 0;
  708.     for (i=2 ; i<w->numpoints ; i++)
  709.     {
  710.         VectorSubtract (w->points[i-1], w->points[0], d1);
  711.         VectorSubtract (w->points[i], w->points[0], d2);
  712.         CrossProduct (d1, d2, cross);
  713.         total += 0.5 * VectorLength ( cross );
  714.     }
  715.     return total;
  716. }
  717.  
  718. /*
  719. =============
  720. Winding_Bounds
  721. =============
  722. */
  723. void Winding_Bounds (winding_t *w, vec3_t mins, vec3_t maxs)
  724. {
  725.     vec_t    v;
  726.     int        i,j;
  727.  
  728.     mins[0] = mins[1] = mins[2] = 99999;
  729.     maxs[0] = maxs[1] = maxs[2] = -99999;
  730.  
  731.     for (i=0 ; i<w->numpoints ; i++)
  732.     {
  733.         for (j=0 ; j<3 ; j++)
  734.         {
  735.             v = w->points[i][j];
  736.             if (v < mins[j])
  737.                 mins[j] = v;
  738.             if (v > maxs[j])
  739.                 maxs[j] = v;
  740.         }
  741.     }
  742. }
  743.  
  744.  
  745. /*
  746. =================
  747. Winding_PointInside
  748. =================
  749. */
  750. int Winding_PointInside(winding_t *w, plane_t *plane, vec3_t point, float epsilon)
  751. {
  752.     int i;
  753.     vec3_t dir, normal, pointvec;
  754.  
  755.     for (i = 0; i < w->numpoints; i++)
  756.     {
  757.         VectorSubtract(w->points[(i+1) % w->numpoints], w->points[i], dir);
  758.         VectorSubtract(point, w->points[i], pointvec);
  759.         //
  760.         CrossProduct(dir, plane->normal, normal);
  761.         //
  762.         if (DotProduct(pointvec, normal) < -epsilon) return false;
  763.     }
  764.     return true;
  765. }
  766.  
  767. /*
  768. =================
  769. Winding_VectorIntersect
  770. =================
  771. */
  772. int Winding_VectorIntersect(winding_t *w, plane_t *plane, vec3_t p1, vec3_t p2, float epsilon)
  773. {
  774.     float front, back, frac;
  775.     vec3_t mid;
  776.  
  777.     front = DotProduct(p1, plane->normal) - plane->dist;
  778.     back = DotProduct(p2, plane->normal) - plane->dist;
  779.     //if both points at the same side of the plane
  780.     if (front < -epsilon && back < -epsilon) return false;
  781.     if (front > epsilon && back > epsilon) return false;
  782.     //get point of intersection with winding plane
  783.     if (fabs(front-back) < 0.001)
  784.     {
  785.         VectorCopy(p2, mid);
  786.     }
  787.     else
  788.     {
  789.         frac = front/(front-back);
  790.         mid[0] = p1[0] + (p2[0] - p1[0]) * frac;
  791.         mid[1] = p1[1] + (p2[1] - p1[1]) * frac;
  792.         mid[2] = p1[2] + (p2[2] - p1[2]) * frac;
  793.     }
  794.     return Winding_PointInside(w, plane, mid, epsilon);
  795. }
  796.  
  797.